/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
};
*/

class Solution {
    public Node flatten(Node head) {
        if(head == null) {
            return null;
        }
        a(head);
        return head;
    }
    public Node a(Node node) {
        Node cur = node;
        Node last = node;//记录最后一个节点
        while(cur != null) {
            Node next = cur.next;
            if(cur.child != null) {
                //如果孩子存在，递归，定义一个新的节点
                Node childLast = a(cur.child);
                 
                next = cur.next;//如果递归多次，保证这个next是上一层的next
                cur.next = cur.child;
                cur.child.prev =cur;//这两行代码是使cur和孩子之间前后联系

                if(next !=  null) {//如果不为空，使next和孩子之间前后联系
                    childLast.next = next;
                    next.prev = childLast;
                }

                cur.child = null;//已经扁平化，质空
                last = childLast;
            } else {
                last = cur;
            }
            cur = cur.next;
        }
        return last;//保证递归完成后，还在上一层递归的下一个
    }
 }